﻿#pragma once //多次包含，避免重定义
#include <iostream>
#include <assert.h>
#include <time.h>
#include <assert.h>
#include <algorithm>
#include <unordered_map>

#include <thread>
#include <mutex>

#ifdef _WIN32
	#include <windows.h>
#else
//....
#endif

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREE_LIST = 208;
static const size_t NPAGE = 129;
static const size_t PAGE_SHIFT = 13;//每个页的大小为8K  *8K = 8*1024 = 2^13，相当于左移13位

//谁亮谁起作用，在32位环境下，运行第二个，在64位环境下运行第一个
#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif

	// 直接去堆上按⻚申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE); //128 * 8 K
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}





static void*& NextObj(void* obj)
{
	return *(void**)obj;//返回的是这块空间的引用，引用返回 返回的是对象本身，返回后可读可写，注意如果返回的对象是临时对象，不能使用引用返回
}


//管理切分好的小对象的自由链表
class FreeList
{
public:
	//桶后面是切分好的小对象，整体的一个对其规则

	// [1,128]				8byte对⻬		freelist[0,16)
	// [128+1,1024]			16byte对⻬		freelist[16,72)
	// [1024+1,81024]		128byte对⻬		freelist[72,128)
	// [8*1024+1,641024]	1024byte对⻬	freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬	freelist[184,208)
	// 也就是说，在64位下，前128个桶中只能存储一个地址大小的空间
	void Push(void* obj)
	{
		assert(obj);//避免加入的空间为nullptr
		//头插
		// *(void**)obj = _freeList// 强转为(void**)是为了兼容32位和64的情况 *obj  指向它原本对应的空间，将其前4/8位修改为下一个节点的地址
		NextObj(obj) = _freeList;
		_freeList = obj;//更新头节点，obj为新的头节点，该头节点的前4/8位指向下一个节点
		++_size;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList; //头插多节点，将原来链表指向的节点地址传给新链表尾节点的前4/8个地址处
		_freeList = start;
		_size += n;
	}

	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList ;//

		_freeList = NextObj(obj);//_freeList 头4/8个字节是下一个节点的地址,将下一个节点的地址 给给 _freeList，此时就完成了头删操作

		--_size;
		return obj;//obj的地址是要给外部用的
	}


	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);//??
		start = _freeList;
		end = start;

		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t Size()
	{
		return _size;
	}

	size_t& MaxSize() //传引用返回，返回就是这个变量自身
	{
		return _maxSize;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};


//对其规则
class SizeClass
{
public:
	// 整体控制在10%的浪费，第一个桶除外
	// [1,128]				8byte对⻬		freelist[0,16)
	// [128+1,1024]			16byte对⻬		freelist[16,72)
	// [1024+1,81024]		128byte对⻬		freelist[72,128)
	// [8*1024+1,641024]	1024byte对⻬	freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬	freelist[184,208)


	//具体确定对齐值的函数
	/*size_t _RoundUp(size_t size, int AlignNum)
	{
		size_t alignSize;
		if (size % AlignNum != 0)
		{
			alignSize = (size / AlignNum + 1) * AlignNum;
		}
		else
		{
			alignSize = size;
		}
		return size;
	}*/

	//大佬写法, 对于+-*/    计算器对位运算的处理更快！
	static inline size_t _RoundUp(size_t size, size_t AlignNum)
	{
		return (size + AlignNum - 1) & ~(AlignNum-1);
		// 其中 bytes是要申请的字节数，alignNum是对应的对齐数
		// 以bytes = 1~8     alignNum = 8 为例
		// 1 + 8 = 9 → 01001  7 + 15→ 01111 均大于8 保证了第四位一定为1
		// 8 - 1 = 7 = 00111  ~7 = 11000  保证了低三位都是0
		// 因此两者相与时，只有第四位是1，即1000 = 8；
	}

	//确定所需开辟空间的对齐规则
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);//申请不同字节数，对应不同的对齐方式
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 128 * 1024)
		{
			 return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1<<PAGE_SHIFT);
		}
	}


	//确定在哪个桶里，普通人写法，这个写法AlignNum 是对齐数，下面是对其实对应2的几次方！
	/*static inline size_t _Index(size_t bytes, size_t AlignNum)
	{
		if (bytes % AlignNum == 0)
		{
			return bytes / AlignNum - 1;
		}
		else
		{
			return bytes / AlignNum;
		}
	}*/

	//大佬写法
	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		//1 + 7  = 8  >> 三位 = 1   -1 = 0
		//8 + 7 = 15  >> 三位 = 1   -1 = 0   即当申请的字节数为1~8时，桶中对应下标为0
	}

	//确定在哪个桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 }; //每次要加上前面对其规则所有的桶数，再加当前偏移量，就能得到对应桶数
		if (bytes <= 128) {
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024) {
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8*1024) {
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024) {
			return _Index(bytes - 8 * 1024, 10) + group_array[2] +
				group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024) {
			return _Index(bytes - 64 * 1024, 13) + group_array[3] +
				group_array[2] + group_array[1] + group_array[0];
	
		}
		else {
			assert(false);
		}
		return -1;
	}

	// ⼀次thread cache 从中⼼缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，⼀次批量移动多少个对象的(慢启动)上限值
		// ⼩对象⼀次批量上限⾼
		// ⼩对象⼀次批量上限低
		int num = MAX_BYTES / size;//1.申请的字节很大，那么这个数就会小，对应的就去大Span少申请点空间
		if (num < 2)
			num = 2;
		if (num > 512)	//2.申请的字节很小，那么这个数就会很大，对应就去小span申请空间
			num = 512;
		return num;//3.其他情况就无所谓
	}

	//central cache 一次向系统获取几个页
	//单个对象8字节
	static size_t NumMovePage(size_t size) //size 表示单个对象的大小
	{
		size_t num = NumMoveSize(size); //如果这里的size = 8 字节，那么num = 512
		size_t npage = num * size;      //  npage = 8 * 512 = 4096 = 4 k   注：一个页8k
		 
		npage >>= PAGE_SHIFT;			//  4096 = 2^12   右移13个字节 = 0； 如果对齐数是16，那刚好够申请一个页，如果对齐数是128 那就是申请8页，
		if (npage == 0)
			npage = 1;
		return npage;			
	 }
};


//管理多个连续页的大块内存跨度结构
//这个是单个span内中的小对象空间，将来分给thread cache的
struct Span
{
	//32位下，地址空间为4GB，每个页框大小为8kb， 2^32 / 2^13 = 2^19个页 ，会有2^19个编号
	//64位下，页号就和夸张了，  2^64 / 2^13 = 2^51个页，会有2^51个编号
	// 通过条件编译来控制 _pageId的类型         在32位下，他是四字节，在64位下，他是八字节，正好对应指针大小         
	//页号
	PAGE_ID _pageId = 0;//一页的大小为8kb，堆地址从0开始，地址/8kb 得到对应页号.
	size_t _n = 0;		//大块页的数量

	Span* _next = nullptr;	//双向链表结构
	Span* _prev = nullptr;

	size_t _ObjSize; //切好的小对象的大小

	size_t _useCount = 0; //切好的小块内存，被分配给thread cache的计数 
	void* _freeList = nullptr ;  //切好的小块内存的自由链表，thread cache 向central cache 申请空间时，找有自由链表的span，即_freeList 不为空

	bool _isUse = false; //是否在被使用
};

//带头双向循环链表
//这个是central cache 哈希桶的结构，区别于thread cache 他是一个双链表结构，为的是：前后找哪个span中有剩余空间，因为当我遍历到链表尾部时，前面的空间可能已经用完换回来了，所以得具备向前找的功能
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}

	//central cache 没有空间时，向page cache要
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}


	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void PushFront(Span* in)
	{
		Insert(Begin(),in);
	}

	Span* PopFront()
	{
		Span* front = _head->_next;
		Erased(front);

		

		return front;
	}

	//将central cache中 pos位置的span“删除”，归还给page cache 
	void Erased(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;

		//delete pos; 不要delete 因为要还给下一层的page cache
		
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	
private:
	 Span* _head;
public:
	std::mutex _mtx;//这个锁的目的是：避免两个线程对central cache中的同一个桶申请空间
};